package net.tp.algo.sort;

public class MergeSort {
    public static void sort(int[] a) {
        sort(a, 0, a.length - 1);
    }

    public static void sort(int[] a, int lo, int hi) {
        if (hi <= lo) return;

        int mid = (lo + hi) >>> 1;
        sort(a, lo, mid);
        sort(a, mid+1, hi);

        merge(a, lo, mid, hi);
    }

    public static void merge(int[] a, int lo, int mid, int hi) {
        if (hi <= lo) return;
        if (mid < lo || mid > hi) throw new IllegalArgumentException();

        int[] b = new int[mid - lo + 1];
        System.arraycopy(a, lo, b, 0, b.length);
        int left = 0, right = mid+1;
        for (int i = lo; i <= hi; i++) {
            if (left == b.length) break;
            else if (right > hi) {
                System.arraycopy(b, left, a, i, hi - i + 1);
                break;
            }
            else if (b[left] <= a[right]) a[i] = b[left++];
            else a[i] = a[right++];
        }
    }
}
